package leetcode.stack_queue;

import java.util.ArrayDeque;

public class Lc82 {

    public ListNode deleteDuplicates(ListNode head) {
        ArrayDeque<ListNode> stack = new ArrayDeque<>();
        ListNode nhead = new ListNode(1000);
        stack.push(nhead);
        while (head != null) {
            if (head.val != stack.peek().val) {
                stack.peek().next = head;
                stack.push(head);
                head = head.next;
            } else {
                while (head != null && stack.peek().val == head.val) {
                    head = head.next;
                }
                stack.pop();
                stack.peek().next = head;
            }
        }
        return nhead.next;
    }
}
 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }